package leetcode2;

public class LargestAltitude {
    public int largestAltitude(int[] gain) {
        int len = gain.length;
        int[] dp = new int[len + 1];
        dp[0] = 0;
        for (int i = 1; i <= len; i++) {
            dp[i] = dp[i - 1] + gain[i - 1];
        }
        int ans = dp[0];
        for (int j = 1; j < dp.length; j++) {
            if (dp[j] > ans) {
                ans = dp[j];
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        LargestAltitude largestAltitude = new LargestAltitude();
        int[] gain = {44, 32, -9, 52, 23, -50, 50, 33, -84, 47, -14, 84, 36, -62, 37, 81, -36, -85, -39, 67, -63, 64, -47, 95, 91, -40, 65, 67, 92, -28, 97, 100, 81};
        largestAltitude.largestAltitude(gain);
    }
}
